\chapter{Game Domain and Mechanics} \label{chap:domainmechanics}
StarCraft is a complex game and it is best described in different parts. The game can be divided into Macromanagement and Micromanagement. This chapter will detail specifically Micromanagement mechanics, what available information is important to consider and how a computer can potentially outplay a human at Micromanagement.

\section{Macromanagement}
Macromanagement is making high level decisions during a match. These decisions entails as to what buildings to build, when to attack, when to scout, and in general strategical and tactical decisions. A big part of these decisions is what to use your accumulated resources on, and when one should try to increase the income by expanding to a new base. An example of when it is wise to expand is when attacking the enemy, so that the enemy does not have the opportunity to attack your new base while it is undefended.

While having a thought out plan about what to build at the start of the match is good, being able to adapt to new information during a match is even more important. If you are able to spot your opponent's buildings or units you can figure out what his plans are, and adapt to counter him. This is some of the reason why the game is so complex, your opponent can do something that you have never seen before, or pretending to do something else than what he is really doing. This high level of reasoning is called the \textit{meta-game}.

In this project we are collaborating with another group, and they will be handling the Macromanagement part of the game. This gives the opportunity to focus exclusively on Micromanagement, which is described in the following subsection. 

\section{Micromanagement} \label{sec:micromanagement}
Micromanagement is the activity of controlling units during a battle. Doing this well requires a lot of skill and concentration. While it is possible to play StarCraft without prioritizing Micromanagement, doing so helps immensely because it will allow the player to be cost effective with his units \citep{sandberg2011evolutionary}. Positioning one unit in the wrong place can decide whether you loose or win a combat engagement, which again can decide if you win or loose the match. The game has a simple path algorithm which positions your units for you when you are moving in to attack an enemy, but the positioning is rarely optimal because the algorithm only considers finding the shortest path from A to B.

The most important Micromanagement techniques are; positioning, focusing fire, withdrawing units temporarily, and keeping units alive. Being able to execute these three puts you at a great advantage over players who can't, as you can be more cost-effective.

\subsection{Positioning}  \label{sub:positioning}
Positioning involves where different types of units stand in relation to each other, the enemy and the environment. Examples of positioning are that weaker units should stand behind stronger units for protection, and units that want to be healed needs to stand within attack range of healing units. In the latter case the attack is a healing attack that replenishes HP, not one that does damage. Units should stand in such a way that they can attack the enemy while still having the ability to retreat. Standing on higher ground makes your units' attacks stronger. 

Where your units should stand varies on the situation they are in. At some times your units should be spread to avoid area of effect attacks, at other times they should be grouped together so not to be picked off by enemy units. The numerous behaviours needed as well as the complexity of each behaviour makes it a difficult problem implementation-wise. Both the positions and the types of enemy units needs to be considered. It is also more general than the other techniques mentioned, and thus a bigger task to take on.

\subsection{Focus Fire} \label{sub:focusfire}
Having your units attack the same enemy unit, is called focus fire, and will let you take down the enemy units more effectively. Which types of units you focus on first is important as some units can be killed fast but have very strong attacks. Taking down units that are close to dying is also important as they can keep attacking at full strength until they are dead. 

The challenge here is to make sure focus firing is happening without putting your units at a greater than necessary risk. Which means that you should attack weak units but not if it means running through a a group of enemy units to do so. Of course, the pros and cons of doing any move in StarCraft are numerous. 

\subsection{Retreating} \label{sub:retreating}
Each unit has a cooldown between attacks, which is the time it takes to reload the weapon. When a unit is on cooldown it is unable to attack until the cooldown wears off. Moving out of range of enemy units when on cooldown lets the unit avoid damage like Figure~\ref{fig:micro_retreat} shows.  If this is exploited and your enemy fails to exploit it one has a great advantage. These techniques are very useful, but also hard to do for a human player because you usually control numerous units at a time. For example the task of selecting a single unit from a group of 50 and Micromanaging it while having to Macromanage is a difficult task. Especially since you would want to retreat several units every second for the whole duration of the battle. A computer is able to do these tasks effortlessly and with millisecond precision, this is further explained in Subsection~\ref{subsec:apm}.

When using a computer each of these tasks can have their own processes (see Section~\ref{sec:architecture}) and acting with millisecond precision is possible.

\begin{figure}[h!]
	\includegraphics[width=\linewidth]{img/micro_retreat.png}
	\caption[Retreat micro technique]{These two screenshots shows a Dragoon attacking and moving away from a Zealot. Dragoon is able to exploit its superior attack range by moving away from the Zealot while the Dragoon is on cooldown.}
	\label{fig:micro_retreat}
\end{figure}

The challenge here is to do the move effectively. The unit should move out of range for just long enough, so that it can attack at once when the cooldown wears off. If enemy units follow it this becomes increasingly difficult, especially if the result is that the unit has to run far before the cooldown wears of. If this leads the unit to be backed up against the wall it is at a disadvantage larger than that of being on cooldown.

Micromanagement is a problem where each instance in time have almost an endless search space of possible moves and outcomes, and shows really how complex RTS games are. Brute forcing this problem is out of the question, as even determining if an action at an instance is optimal is impossible to determine. The best we could hope for would be a solution where good guesses can be made in any situation. In other words a highly dynamic solution. 

\subsection{Staying alive} \label{sub:alive}
Keeping units alive is very important as a damaged unit can still do damage to enemy units, but a dead one cannot. Because of this one often wants to pull damaged units away if they're being attacked. If not explicitly controlled a unit will attack the closest unit of the opposing team within attack range. This means that if a damaged unit is pulled away, the enemy unit(s) attacking it might shift focus to another one of your unit. Hopefully one with more HP. 

Other ways to make sure your units stay alive is attacking with undamaged units first. To do this technique an AI one would have to make sure a unit changes its behaviour when it is damaged in such a way that it would be more careful than the undamaged units. Thus staying alive for longer than it would otherwise.

\section{Attributes}  \label{sec:attributes}
StarCraft is a highly complex domain and it is important to objectify it to understand how the methods presented in Chapter \ref{chap:theorymethodology} can be used to effectively solve the problem of Micromanagement. Relevant information that can be abstracted and used in Micromanagement will be discussed here.

A map in StarCraft should be perceived as a grid. The positions on this grid are represented by two dimensional coordinates x and y, where there is one coordinate for each pixel on the grid. The map can vary in size and usually contains various forms of terrain: flat terrain; low- and high ground; ramps that provide a way to move from low- to high ground and impassable obstacles. All information about the size and shape of the terrain is final and is known to every player. It is important to note that vision from low- to high ground is greatly reduced, giving advantage to anyone fighting on the high ground onto the low ground. Chokepoints are narrow areas, and a group of units within the chokepoint will be at a disadvantage against a group of enemy units of the outside. This is because the units in the chokepoint will not be able to spread out so all units can attack simultaneously. \todo{Bedre å sette lenger nede får sensor kan forstår bevegelse av enheter på et kart?} Such factors are important to analyse when entering a combat, and it is easy to located the coordinates of these choke point by using terrain analysing features in the API. 

To objectify the domain we will determine the properties and variables of it. Properties are constant while variables can vary for each timestep. First the objectification of the map will be shown to give an understanding on how the basic information flow works. Like where a unit can walk and how this data is presented in BWAPI which will be presented in Chapter~\ref{chap:tools}. The most important thing to take away from these properties and variables are what a position on the map means. afterwards the properties and variables directly related to Micromanagement will be presented, as they are important for understanding the solution.

\begin{itemize}
  \item Obstacles \textit{(property)}
  \item Ramps \textit{(property)}
  \item Chokepoints \textit{(property)}
  \item Low Ground \textit{(property)}
  \item High Ground \textit{(property)}
  \item Mineral Deposits \textit{(property)}
  \item Vespene Geysers \textit{(property)}
  \item Units \textit{(variable)}
  \item Buildings \textit{(variable)}
\end{itemize}

A property is the property of the terrain at the position in question. All positions are either defined as high- or low ground, but can only have one more property. Either that it is an obstacle, a ramp, that it is in a chokepoint or that it is clear terrain. Mineral Deposits and Vespene Geysers area have a constant position but they  gradually decrease in value (amount of remaining resources) as they are gathered from. Units and buildings are variables in the way that they are not constant in any position or in the game. All units, and some buildings, can move around and all units and buildings can be destroyed. Only one unit or building can be in the same position at once, with the exception of workers when gathering minerals. 
	
A player will always have complete information about his own units. Information about enemy units are available as long as they are not covered by the fog of war. This includes not only their coordinates and velocity, but also a series of variables and properties that can be exploited and used in calculations to determine Micromanagement decisions or analysis. The properties and variables of special interests are:

\begin{itemize}
  \item Armor \textit{(property)}
  \item Cooldown \textit{(property)}
  \item Attack damage \textit{(property)}
  \item Attack range \textit{(property)}
  \item Movement speed \textit{(property)}
  \item HP \textit{(variable)}
  \item Remaining\_cooldown \textit{(variable)}
  \item Position\_coordinate \textit{(variable)}
\end{itemize}

Properties of units is information that do not change, with a few exceptions that are not relevant to the solution. While variables are observed data that is unique and can change every timestep. The properties show the relative strength of the unit as discussed in Subsection \ref{sub:units}, and the aggregated strength of enemy and friendly units is important for deciding if to attack or run away from a combat engagement. The variables are real-time information and useful for Micromanagement decisions, especially the position coordinate because it can be used to calculate the distance to the unit. When combined with attack range the distance gives information about if an enemy unit can attack the unit, if the unit can attack the enemy unit and how far it has to move for any of these to happen. 

\subsection{Actions Per Minute} \label{subsec:apm}
\textit{Actions per minute} (APM) is a common term in the RTS genre. It is a measurement for the speed or frequency at which a player is able to interact with the game. It does not directly correspond to the skill of a player, but it can show how aware a player is, the intensity of a situation and how fast the player is able to carry out the actions that needs to be done. Typical APM ranges from 20 for beginners to about 300 for professional gamers \footnote{http://wiki.teamliquid.net/starcraft/Actions\_per\_Minute}. This is a game mechanic where an AI can easily reach inhuman capabilities, some StarCraft AIs have a recorded APM of several thousand \footnote{Recorded footage of AIIDE StarCraft AI Competition contestants are freely available on YouTube}.

\subsection{Functions}
Section~\ref{sec:attributes} has so far covered the detailed, low-level data that can be abstracted from the game. This subsection will elaborate on how this information can be used in computations to make decisions in Micromanagement.

As implied in Subsection~\ref{subsec:apm} there is great potential for AI in RTS when it comes to multi-tasking and speed. A human player will consider and use most of the information available to a degree when doing Micromanagement, but it is impossible for him to observe all the information at the same time. An AI will on the other hand be able to measure everything precisely and control all the units with the same precision. This is the main advantage an AI has over a human player. It lacks the complex reasoning ability a human has, but can make up for it with superior oversight and unit control. 
 
For the AI to be able to make Micromanagement decisions in StarCraft it needs to use the properties and variables related to Micromanagement. There are several key equations that will enable the AI to execute the Micromanagement techniques. One such equation uses the relationship between attack ranges and distance. To explain this $MSD$ will be defined as the unit's maximum attack range, $eMSD$ as the enemy unit's maximum shooting distance and $distance$ as the $distance$ between then two units. 

If $MSD - eMSD > 0$ the unit will be able to attack the enemy unit without being hit itself, as long as it pulls back after it has attacked. It can attack again when the remaining cooldown is $0$. This is the retreating technique (see Subsection \ref{sub:retreating}). On the other hand if $MSD - eMSD < 0$ the unit will be in the opposite position and risk getting hit far more times than the opponent. If $MSD << eMSD$ the retreating technique cannot be executed and attacking without retreat is the best tactic, because the unit will not be able to take advantage of the MSD difference. Using the $distance$ variable, found by calculating the vector between two coordinates the following equation can be created:
\begin{equation}
distance - eMSD > 0
\end{equation}
This function can be used as a boolean expression, outputting True if the unit is outside the enemy's attack range and False if it is inside it. 

The $remaining\_cooldown$ variable is important in relation to what actions the unit should take. If on cooldown ($remaining\_cooldown > 0$) the unit should pull away from the enemies' attack ranges to avoid getting hit unnecessarily. When on cooldown the unit should attack an enemy unit as soon as possible, since not doing this right away reduces the total damage output of the unit. This implies that if a unit is to pull away from enemy attack ranges it still has to be close enough so it can attack once the cooldown is finished. The following function can be used to distinguish between being on cooldown and not being on cooldown:
\begin{equation}
remaining\_cooldown > 0
\end{equation}

The HP variable can be used to determine which enemy to take down in an engagement, as well as determine if the unit needs to be more careful (if it's HP is low). The less HP an enemy unit has the fewer attacks are needed to destroy it and the sooner it dies the sooner it is no longer able to attack. If several friendly units were to focus on the same enemy it would also be destroyed quicker. Looking at the HP of a friendly unit on the other hand can be used to determine if the unit should put more focus on staying alive, as discussed in the previous section. To create functions to represent the HP of friendly and enemy units the following variables are defined: $HP$ as the unit's HP, $eHP$ as the enemy's HP and $max(X)$ as the maximum value of variable $X$.

\begin{gather}
1-\frac{eHP}{max(eHP)} \label{eq:ehp} \\
1-\frac{HP}{max(HP)} \label{eq:hp}
\end{gather}

By $\frac{HP}{max(HP)}$ you get the percentage of the remaining HP of the unit. So each of the equations' output increases as the HP of the unit decreases. This is useful to emphasize low HP.

Equation~\ref{eq:ehp} returns a high value when the enemy unit's HP is low. This can be used to target enemy units with low HP, as described in Subsection \ref{sub:focusfire}.

Equation~\ref{eq:hp} returns a high value when the unit's HP is low. When a friendly unit's HP is low measures should be taken to make it stay alive, as discussed in subsection \ref{sub:alive}. 

This chapter has covered the more advanced aspects of StarCraft, the next chapter will cover related research in this domain and how previous StarCraft AI's has used some of some of the information presented here.